package offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution38 {
    List<String> res;
    boolean[] visited;

    public String[] permutation(String s) {
        res = new ArrayList<>();
        visited = new boolean[s.length()];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        dfs(arr, new StringBuilder(), 0);
        return res.toArray(new String[0]);
    }

    private void dfs(char[] arr, StringBuilder stringBuilder, int length) {
        if (length == arr.length) {
            res.add(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (visited[i] || (i > 0 && !visited[i - 1] && arr[i - 1] == arr[i])) {
                continue;
            }
            visited[i] = true;
            stringBuilder.append(arr[i]);
            dfs(arr, stringBuilder, length + 1);
            stringBuilder.deleteCharAt(length);
            visited[i] = false;
        }
    }
}
